package zuochengyun;

//所有的数都出现K次，找到只出现一次的数
public class OnceNum {

	public static void main(String[] args) {
		int[] arr = {1, 1, 1 , 1, 0, 1};
		OnceNum object = new OnceNum();
		System.out.println(object.getNumFromKSysNum2(arr, 2));
		System.out.println(object.onceNum(arr, 5));
		
	}
	
	/**
	 * 核心思想就是K进制下的不进位加法，比如7进制下的无进位相加
	 * a :  6  4  3  2  6  0  1
	 * b :  3  4  5  0  1  1  1
	 * res: 2  1  1  2  0  1  2
	 * K个相同的数的K进制相加的结果一定是每一位都是0的K进制数
	 * @return
	 */
	public int onceNum(int[] arr, int k){
		//eO是一个32位的K进制数
		int[] eO = new int[32];
		for(int i = 0; i < arr.length; i++){
			setExclusiveOr(eO, arr[i], k);
		}
		int res = getNumFromKSysNum2(eO, k);
		return res;
	}
	
	public void setExclusiveOr(int[] eO, int value, int k){
		//将value转换到K进制下的值，每一位都用一个int来存储
		int[] curKNum = getKSysNumFromNum(value, k);
		for (int i = 0; i != eO.length; i++) {
			//两个K进制位的数c 和  d, 在i位上无进位相加的结果是 ( c(i) + d(i)) % k;
			eO[i] = (eO[i] + curKNum[i]) % k;
		}
	}

	public int[] getKSysNumFromNum(int value, int k) {
		int[] res = new int[32];
		int index = 0;
		while(value != 0){
			//数组的开头存储着最低位
			res[index++] = value % k;
			value /= k;
		}
		return res;
	}
	
	/**
	 * 将K进制下的数转换回来(10进制)
	 * @param eO  eO的首位存储着K进制下的最低位
	 * @param k  K进制
	 * @return
	 */
	public int getNumFromKSysNum(int[] eO, int k){
		int res = 0;
		int m = 1;
		for (int i = 0; i < eO.length; i++) {
			res = res + eO[i] * m;
			m = m * k;
		}
		return res;
	}
	
	/**
	 * @param eO  eO的首位存储着K进制下的最高位
	 * @param k
	 * @return
	 */
	public int getNumFromKSysNum2(int[] eO, int k){
		int res = 0;
		for (int i = 0; i < eO.length; i++) {
			res = res * k + eO[i];
		}
		return res;
	}
}
